package leetcode.Hot100;

import leetcode.array.findMaxLength;

import java.util.HashMap;

/**
 * @author Cheng Jun
 * Description: 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
 * https://leetcode-cn.com/problems/subarray-sum-equals-k/
 * @version 1.0
 * @date 2021/11/13 23:14
 * 面试题
 * @see findMaxLength
 */
public class subarraySum {

    public static void main(String[] args) {
        System.out.println(subarraySum1(new int[]{1, -1, 1, -1, 1}, 1));
        System.out.println(subarraySum2(new int[]{1, -1, 1, -1, 1}, 1));

    }

    // 两层嵌套 for 循环，找到每个元素 所有的子序列。再寻找子序列的同时计算子序列和 subSum，和等于k，counter++
    static int subarraySum1(int[] nums, int k) {
        int counter = 0;
        for (int i = 0; i < nums.length; i++) {
            int subSum = 0;
            for (int j = i; j < nums.length; j++) {
                subSum += nums[j];
                if (subSum == k) counter++;
            }
        }
        return counter;
    }

    // 技巧：前缀和
    // 前缀和 + 哈希表优化，定义pre[i] 为 nums的前i个元素之和（包括i），
    // 那么pre[j] - pre[i] = k = nums[j] + nums[j -1] + ··· + nums[i+1]。将key = pre[i], value = pre[i]值的出现次数 （考虑正负数对冲情况）
    // 每个 pre[j] 都与 k 作差 pre[j] - k, 在 hashmap 有没有，有得到次数。没有不做处理。最后都要将 pre 加入到hashmap中
    static int subarraySum2(int[] nums, int k) {
        int counter = 0;
        HashMap<Integer, Integer> preMap = new HashMap<>();
        int pre = 0;
        // 注意此处必须 先考虑，第一个元素 等于 k 的情况，同时也是满足题解思路中，只要pre 出现，就要存入 hashmap
        preMap.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (preMap.containsKey(pre - k)) {
                counter += preMap.get(pre - k);
            }
            preMap.put(pre, preMap.getOrDefault(pre, 0) + 1);
        }
        return counter;
    }
}
